package org.example.myleet.p477;

/**
 * 对于数组 nums 中的某个元素 val，若其二进制的第 i 位为 11，我们只需统计 nums 中有多少元素的第 i 位为 0，即计算出了 val 与其他元素在第 i 位上的汉明距离之和。
 *
 * 具体地，若长度为 n 的数组 nums 的所有元素二进制的第 i 位共有 c 个 1，n−c 个 0，则些元素在二进制的第 i 位上的汉明距离之和为
 *
 * c⋅(n−c)
 *
 * 复杂度O(n*L)，其中n是元素个数，L是整数的位长
 *
 * 作者：LeetCode-Solution
 * 链接：https://leetcode-cn.com/problems/total-hamming-distance/solution/yi-ming-ju-chi-zong-he-by-leetcode-solut-t0ev/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class Solution {

    public int totalHammingDistance(int[] nums) {
        int sum = 0;
        for (int i = 32; i > 0; --i) {
            int c = 0;
            for (int j = 0; j < nums.length; ++j) {
                c += ((nums[j] >> i) & 1);
            }
            sum += (c * (nums.length - c));
        }
        return sum;
    }

//    public int totalHammingDistance(int[] nums) {
//        int sum = 0;
//        for (int i = 32; i > 0; --i) {
//            int c = 0;
//            for (int j = 0; j < nums.length; ++j) {
//                int nj = nums[j];
//                if (((nums[j] >> 1 << 1) ^ nj) == 0) {
//                    ++c;
//                }
//                nums[j] >>= 1;
//            }
//            sum += (c * (nums.length - c));
//        }
//        return sum;
//    }

//    public int totalHammingDistance(int[] nums) {
//        int sum = 0;
//        for (int i = 0; i < nums.length; ++i) {
//            for (int j = i + 1; j < nums.length; ++j) {
////                sum += hammingDistance(nums[i], nums[j]);
//                sum += Integer.bitCount(nums[i] ^ nums[j]);
//            }
//        }
//        return sum;
//    }

//    private int hammingDistance(int x, int y) {
//        int count = 0, z = x ^ y;
//        while (z > 0) {
//            z = z & (z - 1);
//            ++count;
//        }
//        return count;
//    }

//    public static void main(String[] args) {
//        StringBuilder sb = new StringBuilder();
//        for (int i = 0; i < 10000; ++i) {
//            sb.append(i);
//            sb.append(',');
//        }
//        sb.deleteCharAt(sb.length() - 1);
//        System.out.println(sb.toString());
//    }
}
